package com.leetcode;

/***
 * @author yejf
 * @since JDK7.0
 * @CreateDate 2020年4月20日 下午10:50:00
 * @description 此类用来描述了如何求一个字符串的最长回文字符串
 *
 */
public class LongestHuiWenString {

	/****
	 * 求最长回文字符串,为了提高效率，从最长的子串开始判断，如果长的子串是回文字符串，则后面就无需再判断了
	 * 一个长度为n字符串的子串的组合有：1+2+3+...+n 种 我们从最长子串开始判断 示例 1： 输入: "babad" 输出: "bab" 注意:
	 * "aba" 也是一个有效答案。 示例 2：
	 * 
	 * 输入: "cbbd" 输出: "bb"
	 * 
	 * @param s
	 * @return 本案例是采用暴力法，虽然可以算出结果，但是时间复杂度为O(n^3), 达不要性能要求
	 */
	public String longestPalindrome(String s) {
		// 判断
		if (s == null) {
			return null;
		}
		if (s.trim().length() <= 1) {
			return s;
		}
		// 定义变量来保存结果
		int longest = 0;
		String result = "";
		// 外层循环控制字符串从第几个字符开始求子串
		for (int i = 0; i < s.length(); i++) {
			// System.out.printf("此时：longest=%d, i=%d, result=%s\n", longest,i, result);
			if (longest >= s.length() - i) {
				// System.out.println("后面不用再判断了");
				break;
			}
			// 内层循环从大到小求出所有子串的组合
			for (int j = s.length(); j > i; j--) {
				// 求子串
				String sub = s.substring(i, j);

				// 判断一下，如果这个子串的长度比 longest 小，就跳过本轮循环
				if (sub.length() <= longest) {
					// System.out.println("继续...");
					continue;
				}

				// System.out.println("取到的子串："+sub);
				// 判断子串是否是回文字符串
				if (isPalingrome(sub)) {
					// 记录下来，因为此本轮循环中有可能没有回文字符串，所以还要看后面是否有
					if (sub.length() > longest) {
						// 保存起本次的值
						result = sub;
						// 记录本次的长度
						longest = result.length();
					}
				}
			}
		}
		// 如果循环内没有返回，则表示最长的情况下都没有回文字符串，则返回第一个字母
		return result;
	}

	/*****
	 * 判断此字符串是否是回文字符串 所谓回文字符串，是指正读和反读都一样的字符串
	 * 
	 * @param sub
	 * @return
	 */
	private boolean isPalingrome(String sub) {
		// 利用StringBuilder的reverse方法
		StringBuilder builder = new StringBuilder(sub);
		return builder.toString().equals(builder.reverse().toString());
	}

	/******
	 * 本例采用中心扩展法
	 * 
	 * @param s
	 * @return
	 */
	public String longestPalingrome2(String s) {
		//判断是否是null或长度为0的空字符
		if (s == null || s.length() < 1) {
			return "";
		}
		int start = 0, end = 0;
		//循环
		for (int i = 0; i < s.length(); i++) {
			//
			int len1 = expandAroundCenter(s, i, i);
			int len2 = expandAroundCenter(s, i, i + 1);
			int len = Math.max(len1, len2);
			if (len > end - start) {
				start = i - (len - 1) / 2;
				end = i + len / 2;
			}
		}
		return s.substring(start, end + 1);
	}

	/****
	 * 围着中心进行扩展
	 * 
	 * @param s
	 * @param left
	 * @param right
	 * @return
	 */
	private int expandAroundCenter(String s, int left, int right) {
		int L = left, R = right;
		while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
			L--;
			R++;
		}
		return R - L - 1;
	}

	public static void main(String[] args) {
		LongestHuiWenString ls = new LongestHuiWenString();
		String str = "lcnvoknqgejxbfhijmxglisfzjwbtvhodwummdqeggzfczmetrdnoetmcydwddmtubcqmdjwnpzdqcdhplxtezctvgnpobnnscrmeqkwgiedhzsvskrxwfyklynkplbgefjbyhlgmkkfpwngdkvwmbdskvagkcfsidrdgwgmnqjtdbtltzwxaokrvbxqqqhljszmefsyewwggylpugmdmemvcnlugipqdjnriythsanfdxpvbatsnatmlusspqizgknabhnqayeuzflkuysqyhfxojhfponsndytvjpbzlbfzjhmwoxcbwvhnvnzwmkhjxvuszgtqhctbqsxnasnhrusodeqmzrlcsrafghbqjpyklaaqximcjmpsxpzbyxqvpexytrhwhmrkuybtvqhwxdqhsnbecpfiudaqpzsvfaywvkhargputojdxonvlprzwvrjlmvqmrlftzbytqdusgeupuofhgonqoyffhmartpcbgybshllnjaapaixdbbljvjomdrrgfeqhwffcknmcqbhvulwiwmsxntropqzefwboozphjectnudtvzzlcmeruszqxvjgikcpfclnrayokxsqxpicfkvaerljmxchwcmxhtbwitsexfqowsflgzzeynuzhtzdaixhjtnielbablmckqzcccalpuyahwowqpcskjencokprybrpmpdnswslpunohafvminfolekdleusuaeiatdqsoatputmymqvxjqpikumgmxaxidlrlfmrhpkzmnxjtvdnopcgsiedvtfkltvplfcfflmwyqffktsmpezbxlnjegdlrcubwqvhxdammpkwkycrqtegepyxtohspeasrdtinjhbesilsvffnzznltsspjwuogdyzvanalohmzrywdwqqcukjceothydlgtocukc";
		// String str = "babad";
		//
		long start = System.currentTimeMillis();
		System.out.println(ls.longestPalindrome(str));
		long end = System.currentTimeMillis();
		System.out.printf("耗时：%d\n", end - start);
		//
		System.out.println("------------------------------");
		start = System.currentTimeMillis();
		System.out.println(ls.longestPalingrome2(str));
		end = System.currentTimeMillis();
		System.out.printf("耗时：%d\n", end - start);
	}
}
